Aufgabe: Beschreiben Sie die Sprachen der folgenden regulären Ausdrücke in Worten:

a) (1 + ε)(00^{∗}1)^{∗}0^{∗}

b) (0^{∗}1^{∗})^{∗}000(0 + 1)^{∗}

c) (0 + 10)^{∗}1^{∗}

Lösung:

a) Die Menge aller Zeichenreihen, die keine aufeinander folgenden Einsen enthalten. Erklärung: (00^{∗}1)^{∗}0^{∗} Vor jeder 1 stehen beliebig viele, jedoch mindestens eine 0, nach dieser Eins folgen beliebig viele Nullen. (1 + ε) Die Zeichenreihe wird maximal von einer Eins angeführt. 0^{∗}